home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / aijournl / 1988_04 / april.cde next >
Text File  |  1988-03-25  |  16KB  |  473 lines
  1.  
  2. %-----------------------------------------------------------------------
  3. %-----------------------------------------------------------------------
  4. %          A Simple Query Processor in Prolog
  5. %
  6. %          Author:  Rodger Knaus
  7. %                   Instant Recall
  8. %                   5900 Walton Rd.
  9. %                   Bethesda, Md. 20817
  10. %                   (301) 530 - 0898
  11. %                   BBS: (301) 983-8439 (2400 bps)
  12. %
  13. %          Version of Prolog: Arity Prolog, v. 4
  14. %
  15. %          See the Practical Prolog column in
  16. %          AI Expert (April, 1988) for a discussion of this program
  17. %
  18. %          Note about this listing:  This listing is complete except
  19. %          for a few low level predicates, such as list_length which
  20. %          you can easily write yourself.          
  21. %          
  22. %
  23. %-----------------------------------------------------------------------  
  24. %-----------------------------------------------------------------------
  25. %-----------------------------------------------------------------------
  26. %
  27. %      Listing 1 -- The top Level of a Query Processor
  28. %
  29. %
  30. % Call:  process_query( Field_list, Tables, Conditions)
  31. %
  32. % Purpose:  Retrieves data in the Prolog database specified by
  33. %           Field_list, Tables, and Conditions
  34. %
  35. % Input arguments:
  36. %
  37. %     Field_list = list of fields to be displayed
  38. %
  39. %     Tables = list of predicate names for the facts which
  40. %              contain the fields in Field_list.
  41. %
  42. %     Conditions = a list of boolean conditions which the retrieved
  43. %                  data are to satisfy
  44. %
  45. % Output arguments:
  46. %
  47. %     none
  48. %
  49. % Success conditions:
  50. %
  51. %     Succeeds whenever the input arguments can be translated into
  52. %     a query in Prolog.
  53. %
  54. % Effects:
  55. %
  56. %     When the input arguments can be translated into Prolog, any
  57. %     data retrieved by the query in Prolog is displayed.  If the
  58. %     translation can not be carried out, an error message is
  59. %     displayed.
  60. %
  61. %
  62.           % try to retrieve data
  63.   process_query(Field_list, Tables, Conditions ) :-
  64.           % translate inputs into a Prolog question
  65.       generate_query( Field_list, Tables, Conditions, Generated_goal),!,
  66.           % With the Prolog question, retrieve and display data
  67.       get_all( Field_list,  Generated_goal),
  68.           % Stay with this rule if it succeeds
  69.        !.
  70.  
  71.           % put out error message if previous rule fails
  72.   process_query( Field_list, Tables, Conditions) :-
  73.       nl, write( $Error in process_query for :$),
  74.       nl, write( $Field_list = $ ), write( Field_list ),
  75.       nl, write( $Tables = $ ), write( Tables ),
  76.       nl, write( $Conditions = $ ), write( Conditions ),
  77.       nl, fail.
  78. %
  79. %-----------------------------------------------------------------------
  80. %
  81.  
  82. %----------------------------------------------------------------------
  83. %                                                                     |
  84. %  Listing 2 -- Predicate for Defining a Data Retrieval Predicate     |
  85. %                                                                     |
  86.   generate_query(Field_list, Tables, Conditions, prdbms_goal(X)) :-   %
  87.            % Step 1 -- retract all temporaryy information left from   %
  88.            % processing previous queries                              %
  89.      retract_old_clauses, !,                                          %
  90.            % Step 2 -- construct list of calls for table rows         %
  91.            % that contain the needed information                      %
  92.      get_calls_to_tables(Field_list, Tables, Table_calls),  !,        %
  93.            %  Step 3 -- translate conditions to Prolog                %
  94.      build_conditions_terms( Table_calls, Conditions,
  95.                              Condition_terms),  !,        %
  96.            %  Step 4 -- build list of variables representing
  97.            %             list of fields
  98.      replace_field_names( Table_calls,
  99.                           Field_list,
  100.                           Variable_list),
  101.            %  Step 5 -- term setting variable in rule head
  102.      Goal_term = ( X = Variable_list ),
  103.            %  Step 6 -- build list of terms in prdbms_goal rule body  %
  104.      append_lists( [ Table_calls,                                     %
  105.                      Condition_terms,                                 %
  106.                      [ Goal_term ] ],                                 %
  107.                     Rule_body_as_list), !,                            %
  108.            %  Step 7 -- Build a conjunction of rule body terms        %
  109.      build_conjunction( Rule_body_as_list,  Body ),  !,               %
  110.            %  Step 8 -- assert a new rule for predicate goal          %
  111.      asserta( (prdbms_goal(X) :- Body)) .
  112.  
  113. %                                                                     |
  114. %----------------------------------------------------------------------
  115. %
  116. %---------------------------------------------------------------------------
  117. %
  118. %  Listing 3 -- Retracting Old Information from the Database
  119. %
  120. %/****************** retract_old_clauses *****************************/
  121. %/*
  122. %retract_old_clauses retracts facts and rules which might be left
  123. %   from processing previous user queries.
  124. %*/
  125. %
  126.  retract_old_clauses :-
  127.           % retract rules that are Prolog implementations of old queries
  128.      retract_all_clauses(prdbms_goal, 1),
  129.           % retract old variable dictionary facts
  130.      retract_all( temp_variable_meaning( _ , _)).
  131. %
  132. %/****************** retract_all_clauses *****************************/
  133. %/*
  134. % Call: retract_all_clauses(Functor, Arity)
  135. %
  136. % Purpose:  retracts all clauses whose head has a given functor and arity.
  137. %
  138. % Input arguments:
  139. %
  140. %    Functor:  Functor for the head of rules to be retracted
  141. %
  142. %    Arity:    Arity of functor of head of rules to be retracted
  143. %
  144. % Output arguments: none
  145. %
  146. % Success conditions: always succeeds
  147. %
  148. % Effect:  retracts all clauses with head functor Functor of arity Arity
  149. %
  150. % Example:
  151. %
  152. %   retract_all_clauses(factorial, 2) retracts any rules in the database
  153. %   of the form
  154. %
  155. %         factorial(_,_) :- _.
  156. % */
  157. %
  158.   retract_all_clauses(Functor, Arity) :-
  159.               % build a term with Functor/Arity as functor and
  160.               % all different variables as arguments
  161.          functor(Head, Functor, Arity),
  162.               % build a rule with head Head and arbitrary tail
  163.          Rule = ( Head :- _),
  164.               % retract everything that matches Rule
  165.          retract_all(Rule).
  166. %
  167. %/******************  retract_all ************************************/
  168. % /*
  169. % Call:  retract_all(Form)
  170. %
  171. % Input arguments:
  172. %
  173. %     Form = a Prolog term such that anything which matches it is to be
  174. %            retracted from the Prolog database
  175. %
  176. %     Success conditions:  always succeeds
  177. %
  178. %     Effect:  retracts any clause that matches Form from the database
  179. % */
  180. %
  181.   retract_all(Form):-  retractall(Form).
  182.   retractall(Form):-
  183.      repeat,
  184.        retractall1(Form).   /* Fails until no more patterns match Form */
  185.  
  186.  
  187.              % if there is something in the database matching Form,
  188.   retractall1(Form):-
  189.              % retract it,
  190.            retract(Form),
  191.              % cut to stay in this rule
  192.            !,
  193.              % and fail to cause backtracking back up to get another Form
  194.            fail.
  195.  
  196.              % if nothing else matches Form, then succeed
  197.   retractall1(_):-!.
  198. %
  199. %
  200. %---------------------------------------------------------------------------
  201.  
  202.  
  203. %---------------------------------------------------------------------------
  204. %
  205. %   Listing 4 -- Replacing Field Names with Values
  206. %
  207. % /*
  208. % Call:
  209. %
  210. %      replace_field_names( Input_structure, Output_structure)
  211. %
  212. % Input argument:
  213. %
  214. %      Input_structure = a Prolog structure containing field names
  215. %
  216. % Output argument:
  217. %
  218. %      Output_structure = the corresponding structure with field names
  219. %                         replaced by variables.
  220. %
  221. % Success conditions:  always succeeds
  222. %
  223. % Side Effects:  none
  224. %
  225. % Example:
  226. %
  227. %     Assumptions:  The database contains
  228. %
  229. %        temp_variable_meaning( item, X1).
  230. %        temp_variable_meaning( quantity, X4).
  231. %
  232. %     Call: replace_field_names( [(item = diskettes),  (quantity > 5) ],
  233. %                                Result)
  234. %
  235. %     On exit:
  236. %
  237. %           Result = [(X1 = diskettes),  (X4 > 5) ]
  238. %
  239. %
  240. % */
  241.              % map variables into themselves
  242.   replace_field_names( _, Input, Input ):-
  243.              var( Input), !.
  244.  
  245.              % map atoms
  246.   replace_field_names( Table_calls, Input, Result):-
  247.          atomic( Input), !,
  248.          replace_field_name_atom( Table_calls, Input, Result).
  249.  
  250.              % map the empty list into itself
  251.   replace_field_names( _, [], []):- !.
  252.  
  253.              % map lists recursively
  254.   replace_field_names( Table_calls, [ H | T ], [H1 | T1 ]):- !,
  255.              replace_field_names( Table_calls, H, H1),
  256.              replace_field_names( Table_calls, T, T1).
  257.  
  258.              % map functor and argument structures
  259.   replace_field_names( Table_calls,  Structure, Result   ):-
  260.              % map structures by first changing them to lists,
  261.         Structure  =.. Input_list,
  262.              % then mapping them,
  263.         replace_field_names( Table_calls,  Input_list, Result_as_list),
  264.              % finally changing them back to structures
  265.         Result =.. Result_as_list, !.
  266.  
  267.              % report error if this rule is reached
  268.   replace_field_names(_, Structure, Structure  ):-
  269.         nl,
  270.         write($This structure could not be mapped by replace_field_names:$),
  271.         nl, write(Structure).
  272.  
  273.   /* Using this predicate we can define the helper predicate
  274.      that translates user-supplied conditions into Prolog                */
  275.  
  276.   build_conditions_terms( Table_calls,
  277.                           Conditions,
  278.                            Condition_terms) :-
  279.          replace_field_names( Table_calls,
  280.                               Conditions,
  281.                               Condition_terms).
  282.  
  283.  
  284. /*  The next predicate maps atoms for 'build_conditions_terms',
  285.     replacing field names with the corresponding variable
  286. */
  287.     % Strategy is recursion on the list of Tables
  288.  
  289.                   % default mapping of an atom is the atom
  290. replace_field_name_atom( [], Input, Input) :- !.
  291.  
  292.                   % try to find the variable for Field in Table
  293. replace_field_name_atom( [Table | Tables], Field, Result) :-
  294.                   % get the name of the functor of Table
  295.             functor(Table, Predicate_name, _),
  296.                   % see if Field is in this table
  297.                   % if so, get its argument Position
  298.             call(has_field( Predicate_name, Field, Position)),  !,
  299.                   % get the corresponding variable Result from Table
  300.             arg(Position, Table, Result).
  301.  
  302.                   % if no success above, try the next table
  303. replace_field_name_atom( [ _ | Tables], Input, Result) :-
  304.            replace_field_name_atom(  Tables, Input, Result).
  305.  
  306.  
  307.  
  308. % |---------------------------------------------------------------------------
  309.  
  310. %-------------------------------------------------------------------------
  311. %
  312. %   Listing 6 -- Building a Conjunction from a List of Terms
  313. %
  314. % /*
  315. % Call: build_conjunction( List, Conjunction)
  316. %
  317. % Input arguments:
  318. %
  319. %      List = a list of terms
  320. %
  321. % Output arguments
  322. %
  323. %      Conjunction = the list of terms ANDed together.
  324. %
  325. % Success conditions:
  326. %
  327. %      Succeeds whenever the input is a list.
  328. %
  329. % Note:  This predicate also works in the opposite direction, converting
  330. %        a conjunction to a list of terms.
  331. %
  332. % */
  333.  
  334.          % the AND of no items is always true
  335.   build_conjunction( [], true):-!.
  336.  
  337.          % the AND of one item is the item itself
  338.   build_conjunction( [Term], Term) :- !.
  339.  
  340.          % Here is the recursive rule
  341.   build_conjunction( [ Term | Terms ], ( Term , Terms_as_conjunction)) :-
  342.                    build_conjunction( Terms , Terms_as_conjunction).
  343.  
  344. %-------------------------------------------------------------------------
  345.  
  346. %----------------------------------------------------------------------
  347. %
  348. %      Listing 7 -- A Data Retrieval Loop
  349. %
  350. % /*
  351. % Call: get_all(Field_list, Goal )
  352. %
  353. % Input arguments:
  354. %
  355. %      Field_list = list of names of user fields
  356. %
  357. %      Goal = goal that finds a single instance of the desired data
  358. %
  359. % Success conditions
  360. %
  361. %      always succeeds
  362. %
  363. % Effects:  displays all instances of data satisfying the user query
  364. % */
  365. %
  366.            get_all(Field_list, Goal ) :-
  367.                 call( Goal ),
  368.                 arg(1, Goal , Value_list),
  369.                 display_item( Field_list, Value_list),
  370.                 fail.
  371.            get_all(_, _ ) :-!.
  372. %
  373. %----------------------------------------------------------------------
  374.  
  375. %------------------- Predicates from body of column --------------------
  376.  
  377.          % gets pattern matching an arbitrary data item in a table
  378.          % Note: this is the special case when there is only one table
  379. get_calls_to_tables(Field_list, [Table], [Table_call]) :-
  380.       find_arity(Table, Arity),
  381.       functor( Table_call, Table, Arity).
  382.  
  383.          % finds the Arity of nTable_name
  384. find_arity(Table_name, Arity) :-
  385.      findall( X, has_field(Table_name, X, _), Fields),
  386.      list_length(Fields, Arity).
  387.  
  388.          % build term that sets output variable in head of generated rule
  389.          % for processing the query
  390. build_goal_output_term( Field_list ,
  391.                         Output_variable,
  392.                         Goal_output_term) :-
  393.              % get list of variables
  394.       replace_field_names( Field_list , Varible_list),
  395.              % build the output term
  396.       Goal_output_term = ( Variable = Varible_list ).
  397.  
  398.  
  399.          % a simple display predicate for a table row
  400. display_item( Field_list, Value_list) :-
  401.        nl, write( Value_list).
  402.  
  403.  
  404. %    Since we are assuming a single table call, we omit the definition
  405. %    of 'find_table_call_for_field'.   In this special case you can use
  406.  
  407. find_table_call_for_field(_, [Table_call], Table_call).
  408.  
  409.  
  410. % -------------------------------------------------------------------------
  411.  
  412. %--------------------  End of program  --------------------------------
  413.  
  414. %------------------ Start of test data and predicates ------------------
  415.  
  416. /********** test database *************************************************/
  417.  
  418. transaction( diskettes, 1, 1/24,  100, 24.95,
  419.              $Dicount Diskettes$, $Visa4$ ).
  420. transaction( 'hard disk',  2,  2/13,   1,  345.00,
  421.              $Computer Serv. Ctr.$, $Visa$).
  422. transaction( eyeglasses, 3, 2/14, 1, 250.00,
  423.              $Dr. Feinberg$, $check 345$).
  424.  
  425. supplier( $Dicount Diskettes$,
  426.          address( [$Box 2314$, $Chicago, Ill.$], _ ),
  427.          [diskettes, ribbons, paper]).
  428. supplier( $Computer Serv. Ctr.$,
  429.          address( [$5211 Nebraska Ave. NW$, $Wash. D.C.$], $20015$ ),
  430.          'hard disk').
  431. supplier( $Dr. Feinberg$,
  432.          address( [$4545 Conn. Ave. NW$, $Wash. D.C.$], $20016$),
  433.          eyeglasses).
  434.  
  435. item( diskettes  , supplies              ).
  436. item( 'hard disk'  , 'capital expenditures'  ).
  437. item( eyeglasses , 'medical expenses'      ).
  438.  
  439. /************************** data dictionary  ******************************/
  440. % This is a data dictionary for the above database
  441.  
  442.  
  443. has_field(transaction, item, 1).
  444. has_field(transaction, id, 2).
  445. has_field(transaction, date, 3).
  446. has_field(transaction, quantity, 4).
  447. has_field(transaction, price, 5).
  448. has_field(transaction, supplier, 6).
  449. has_field(transaction, 'how paid', 7).
  450.  
  451. has_field(supplier, name, 1).
  452. has_field(supplier, address, 2).
  453. has_field(supplier, items, 3).
  454.  
  455. has_field(item, item, 1).
  456. has_field(item, class, 2).
  457.  
  458. /************************** test predicates  ******************************/
  459.  
  460. % This is a test predicate for process_query.  It should produce the
  461. % following output on the screen with the example data above:
  462.  
  463. %  [diskettes, 1/24 ]
  464.  
  465. test  :-
  466.     process_query( [ item , date],
  467.                    [ transaction ] ,
  468.                    =( item, diskettes) ).
  469.  
  470. /********************** end test predicates  ******************************/
  471.  
  472. %------------------- End of listing ------------------------------------
  473.  te